package mo.leetcode_top;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LI1714 {

    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0) {
            return res;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for (int i = 0; i < k; i++) {
            queue.add(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            Integer max = queue.peek();
            if (max > arr[i]) {
                queue.poll();
                queue.add(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            res[k-1-i] = queue.poll();
        }

        return res;
    }


    public static void main(String[] args) {
        LI1714 test = new LI1714();
        System.out.println(Arrays.toString(test.smallestK(new int[]{1, 3, 5, 7, 2, 4, 6, 8}, 4)));
    }
}
